(N o (N in O u A computer based classification of caps in PG(4, 2; Daniele Bartoli, Stefano Marcugini, Fernanda Pambianco Abstract ^ [ In this paper we present the complete classification of caps in PG(4, 2). These results have been obtained using a computer based exhaustive search that exploits projective equivalence. > Q^ ' 1 Introduction p ^ ' 3 of which are collinear. A n-cap is called complete if it is not contained in a (n + l)-cap. ^ . For a detailed description of the most important properties of these geometric structures, we refer the reader to [4j . In the last decades the problem of determining the spectrum of the sizes of complete caps has been the subject of a lot of researches. For a survey see [I]. K^ I In [5] (see Th. 18.2.1) is presented the classification of complete caps in PG{3,2) and it is H ' also possible to understand the classification of the incomplete caps. The following table " " " shows the number of non equivalent complete and incomplete caps in PG{3, 2). In the projective space PG{r, q) over the Galois Field GF{q), a ri-cap is a set of n points no Table 1: Number and type of non equivalent examples /C| # COMPLETE CAPS # INCOMPLETE CAPS 5 6 7 8 1 1 1 1 1 In this work we search for the classification of complete and incomplete caps in PG{A, 2), using an exhaustive search algorithm. In Section |2] the algorithm utilized is illustrated; in Section [3] the complete list of non equivalent complete and incomplete caps is presented. 2 The searching algorithm In this section the algorithm utilized is presented. Our goal is to obtain the classification of complete and incomplete caps in FG(4,2). It is not restrictive to suppose that a cap in PG{4, 2) contains this five points: 7^ = {(1 : : : : 0); (0 : 1 : : : 0); (0 : : 1 : : 0); (0 : : : 1 : 0); (0 : : : : 1)}. Then we define the set Cand of all the points lying no 2-secant of 7^. We introduce in Cand the following equivalence relationship: F~g CU{P}^CU{Q}, where = means that the two sets are projectively equivalent. This relationship spreads the candidates in equivalent classes Ci, . . . ,Ck- The choice of the next point to add to the building cap can be made only among the repre- sentatives of the equivalent classes, in fact two caps one containing C U {P} and the other one C U {Q}, with P and Q in Cj, are equivalent by definition of orbit. Suppose now that we have construct all the caps containing CU{Pj}, with i < i. Considering the caps containing C U {Pj} with i < j, all the points of the classes Ck with k < i can be avoided. In fact a cap containing C U {Pj} U {Pk}, with P^ G Ck and k < i, is projectively equivalent to a cap containing C U {Pk} U {Pj}, already studied. When we add a new point to the cap, we can divide all the remaining candidates in equiv- alence classes, as above. Two points P and Q are in relationship with the j-th class Cj, i.e. P ~j Q, if C U {Pj} U {P} and C U {Pj} U {Q} are projectively equivalent. At the m-th step of the extension process if the cap C U {Pi^} U . . . U |p^*i---*™-i j u |pj jg projectively equivalent to the cap C U {Pi^} U . . . U {/^^■■■^™"'} U {Q} with Pji-^'' G C^i-*'-, then P and Q are in relationship {P ^i^...im Q) and they belong to the same class Cl^^'^l"". Iterating the process we can build a tree similar to the following: Ci Co Ch CI CI cf Cl'^ c 1,1 Cl'' c 2,1 fc2,l c« nk,kk The tree is important to restrict the number of candidates in the extension process. Suppose that we have generated a n-cap containing the cap C U {Pi^ } U {P/^ } U . . . U {P/^"'*™"^ } U {P}, after having generated n-caps containing C U {Pj} with j < ii, C U {Pi^} U [P]^} with i < 22,. . . , C U {PiJ U {P*;!} U . . . U {p^i-^— 1} with j < i„, with P;!-^- G C^-*'-. Then the uc: ^m -1- can points belonging to Ci U . . . U Ci,_i U C}^ U . . . U CY^_^ U . . . U C^ '""^ U be avoided, because a cap containing one of them is equivalent to one already found. For example a n-cap containing C U {P^ J U . . . U {Pt"^"'""'^} U {P} U {Q} with Q eCh for some /i < «! is equivalent to a n-cap containing C U {Pfe}, which is already found. 3 Results In this Section all non equivalent caps, complete and incomplete, in PG'(4, 2) are presented. 3.1 Non-equivalent caps /C in PG(4, 2) This table shows the number and the type of the non equivalent examples of all the caps. Table 2: Number and type of non equivalent examples /C| # COMPLETE # INCOMPLETE CAPS CAPS 6 3 7 3 8 4 9 1 4 10 1 3 11 2 12 2 13 1 14 1 15 1 16 1 All the non equivalent examples of the caps described in the table above are presented. In particular for each cap we compute the stabilizer and the weight enumerators of the associated code. Size Type Cap Weight enumerators G 6 Inc. 10 1 10 1 10 1 10 1 11 21541551 G720 6 Inc. 10 10 10 10 10 110 11 112103104555 G120 6 Inc. 10 1 10 10 1 10 1 10 ^227312475251 G48 7 Inc. 10 10 10 1 10 10 10 11 10 1 2639495671 Gj2 7 Inc. 10 11 10 10 10 1 10 11 110 26312475453 G4S 7 Inc. 110 1 110 10 10 1 10 1 10 Ii233"4ii536i7i G48 8 Inc. 1110 1 10 10 110 10 1 10 1 10 10 244225431 G384 8 Inc. 110 1 1110 10 110 1 10 10 1 10 ^137414577131 GIQ8 8 Inc. 110 11 110 10 10 10 1 10 11 110 2I310411545372 G48 8 Inc. 110 10 110 1 10 10 10 10 11 10 1 2238410585231 G32 Size Type Cap Weight enumerators G 9 Inc. 110 11 1110 10 10 110 1 10 10 11 000000100 114145143191 ^1334 9 Inc. 111000011 110 10 110 10 1 10 11 10 110 34414587431 Gi92 9 Inc. 110 10 110 1 10 110 10 110 11 10 10 1 3649595691 Gr72 9 Inc. 1110 10 110 1 110 10 10 10 11 10 10 1 3133411511537191 6*48 9 Comp. 110 11 1110 10 10 110 1 10 10 11 110 214215732 ^336 10 Inc. 110 110 110 10 1 10 110 10 110 11 10 110 1 415515^01 ^720 10 Inc. 10 110 11 10 111 0010011011 10 110 1 110 10 1 21465165631^0! ^384 10 Inc. 10 10 10 0100001110 0010010111 0001011011 10 10 1 32475125772101 6*48 10 Comp. 1100001011 10 10 10 1 10 1111 10 10 110 10 1110 41051635 ^1920 11 Inc. 10 110 10 1 10 1111 00100110111 10 110 11 110 10 1 31425125127231111 ^192 11 Inc. 110 10 10 110 1110 10 10 111 10 110 11 10 10 10 1 4551051075111 G120 Size Type Cap Weight enumerators G 12 Inc. 100001101101 010000011111 001001100111 000100111011 000011010001 43Q2483121 ^2304 12 Inc. 110000101001 011000011101 000100101111 000010110111 010001010011 4158Q127881121 ^192 13 Inc. 1000011011001 0100000111101 0010011001111 0001001110111 0000110100011 53gl27l283i3l ^576 14 Inc. 11000011011001 01100000111101 00010011001111 00001001110111 01000110100011 Q771687141 ^2688 15 Inc. 110000111011001 011000000111101 000100110001111 000010011110111 010001101100011 715315151 ^20160 16 Comp. 1100001110110001 0110000001111101 0001001100011111 0000100111100111 0100011011001011 gSOlQl ^322560 References [1] A. Davydov, G. Faina, S. Marcugini and F. Pambianco, On size of complete caps in projective spaces PG{n, q) and arcs in planes PG{2, q), Journal of Geometry, published online 18/7/2009. [2] G. Faina, S. Marcugini, A. Milani and F. Pambianco, The size k of the complete fe-caps in PG{n,q) for small q and 3 < n < 5, Ars Combinatoria 50 (1998), 235-243. [3] M. Hall and J. K. Senior, The group of order 2" (n < 6), Macmillan, New York, 1964. [4] J. W. P. Hirschfeld, Projective geometries over finite fields, Claredon Press, Oxford, 1979. [5] J. W. P. Hirschfeld, Finite projective spaces of three dimension, Claredon Press, Oxford, 1985.